package leetcode.f1t100;

import java.util.*;

/**
 * 给一个可重复数组, 返回数组数字的所有排列组合
 * https://leetcode.com/problems/permutations-ii/
 *
 * @Author lichongxiao
 * @Date 2022/10/21 16:15
 */
public class Q47_PermutationsII {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ansList = new ArrayList<>();
        boolean[] flag = new boolean[nums.length];
        Arrays.sort(nums);
        process(nums, flag, new ArrayList(), ansList);
        return ansList;
    }

    private void process(int[] nums, boolean[] flag, List<Integer> numList, List<List<Integer>> ansList) {
        if(numList.size() == nums.length){
            ansList.add(new ArrayList<>(numList));
            return;
        }
        for (int i = 0, length = nums.length; i < length; i++) {
            if(flag[i]){
                continue;
            }
            // 前一个使用了后一个才使用，同值正序试用  a1,a2,a3
            if(i > 0 && nums[i] == nums[i-1] && !flag[i-1]){
                // 前一个使用后一个就不使用，同值逆序试用 a3,a2,a1
//            if(i > 0 && nums[i] == nums[i-1] && !flag[i-1]){
                continue;
            }
            numList.add(nums[i]);
            flag[i] = true;
            process(nums,flag,numList,ansList);
            flag[i] = false;
            numList.remove(numList.size()-1);
        }
    }

    public static void main(String[] args) {
        Q47_PermutationsII bean = new Q47_PermutationsII();
        List<List<Integer>> ansList = bean.permuteUnique(new int[]{1, 1, 2});
        for(List<Integer> ans : ansList){
            for(Integer num : ans){
                System.out.print(num+" ");
            }
            System.out.println();
        }
    }
}
